package ai.zixing.mashibing.new_class.class08;

import java.util.Arrays;

public class Code02_MergeSort {

    public static void main(String[] args) {
        int maxSize = 500;
        int maxValue = 100000;
        int testTime = 1000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] array = generateRandomArray(maxSize, maxValue);
            int[] mergeArr = copyArr(array);
            Arrays.sort(array);
//            mergeSort1(mergeArr);
            mergeSort2(mergeArr);
            if (!isEqual(array, mergeArr)) {
                System.out.println("error=============");
                printArray(array);
                printArray(mergeArr);
                break;
            }
        }
        System.out.println("测试结束");
    }

    public static int[] copyArr(int[] arr) {
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        // 左边有序
        process(arr, L, mid);
        // 右边有序
        process(arr, mid + 1, R);
        // 合并有序
        merge(arr, L, mid, R);
    }

    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        // 第一个指针指向前一半
        int p1 = L;
        // 第二个指针指向后一半
        int p2 = M + 1;
        // 归并移动前后指针
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // p1，p2中有一个会越界,不可能两个都越界
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

    // 无递归实现
    // 操作步长
    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 1;
        int N = arr.length;
        while (step < N) {
            int L = 0;
            while (L < N) {
                int M = 0;
                // L ... N - 1  N -L
                // N - L 可以凑够一组
                if (N - L >= step) {
                    M = L + step - 1;
                } else {
                    M = N - 1;
                }
                if (M == N - 1) {
                    break;
                }
                int R = 0;
                // 右组
                // (N -1) - (M + 1) + 1 = N -1 -M
                if (N - 1 - M >= step) {
                    R = M + step;
                } else {
                    R = N - 1;
                }
                // L...M   M + 1 ... R
                merge(arr, L, M, R);
                if (R == N - 1) {
                    break;
                } else {
                    L = R + 1;
                }
            }
            // N / 2 是向下取整的，如果 N = 17，则最后的步长 step 需要达到 16，但是 N / 2 = 8
            // 如果是 step >= (N / 2)，则 step 取不到 16 ，最后一次没有合并
            if (step > (N / 2)) {
                break;
            } else {
                step *= 2;
            }
        }
    }


    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxSize)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        return arr;
    }

    public static boolean isEqual(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1 != null ^ arr2 != null) {
            return false;
        }
        if (arr1.length != arr2.length) {
            return true;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
